package com.jia.jianzhiOffer;

import java.util.HashSet;
import java.util.Set;

/**
 * 剑指 Offer 52. 两个链表的第一个公共节点
 */
public class Pro52 {
    //hash
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while(headA!=null) {
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null) {
            if(set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
    //浪漫相遇  两指针h1从headA开始走完，然后从headB开始走，
    //同理另一指针h2从headB开始然后从headA开始，那么h1和h2走过同样的路程在相交点相遇
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        ListNode h1 = headA;
        ListNode h2 = headB;
        while(h1!=h2) {
            h1 = h1 == null? headB : h1.next;
            h2 = h2 == null? headA : h2.next;
        }
        return h1;
    }
    //记录headA开始到最后长度，和headB开始到最后长度。
    //减去长的,再一起遍历
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int aLen = 0;
        int bLen = 0;
        ListNode h1 = headA, h2 = headB;
        while(h1 != null) { ++aLen; h1 = h1.next;}
        while(h2 != null) { ++bLen; h2 = h2.next;}
        int sub = aLen - bLen;
        h1 = headA;
        h2 = headB;
        if(sub > 0) {
            while(sub > 0) { h1 = h1.next; --sub;}
        }else {
            while(sub < 0) { h2 = h2.next; ++sub;}
        }
        //together
        while(h1 != h2) {
            h1 = h1.next;
            h2 = h2.next;
        }
        return h1;
    }
}
